package solution;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * <a href="https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=117&&tqId=37722&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking">
 * NC14 按之字形顺序打印二叉树</a>
 *
 * @author or2
 * @Description 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
 * @create 2021年08月31日 时间: 14:22
 */
public class PrintTreeNode {

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        if (pRoot == null) {
            return new ArrayList<>();
        }

        LinkedList<TreeNode> queueOdd = new LinkedList<>();
        LinkedList<TreeNode> queueEven = new LinkedList<>();
        queueOdd.offer(pRoot);
        int level = 1;

        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        while (!queueOdd.isEmpty() || !queueEven.isEmpty()) {
            ArrayList<Integer> levelArray = new ArrayList<>();
            if ((level & 1) == 1) {
                while (!queueOdd.isEmpty()) {
                    TreeNode remove = queueOdd.remove();
                    if (remove == null) {
                        continue;
                    } else {
                        levelArray.add(remove.val);
                    }
                    queueEven.offerFirst(remove.left);
                    queueEven.offerFirst(remove.right);
                }
            } else {
                while (!queueEven.isEmpty()) {
                    TreeNode remove = queueEven.remove();
                    if (remove == null) {
                        continue;
                    } else {
                        levelArray.add(remove.val);
                    }
                    queueOdd.offerFirst(remove.right);
                    queueOdd.offerFirst(remove.left);
                }
            }
            ans.add(levelArray);
            level++;
        }

        ans.remove(ans.size() - 1);
        return ans;
    }


    private static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
}

